package junior.回溯法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * N后问题，1-N的排列，行列都不需要考虑，仅考虑斜线
 */
public class n后问题_多线程 { // 还有问题
    public static void main(String[] args) throws InterruptedException {

        ExecutorService executorService = Executors.newFixedThreadPool(20);
        long l2 = System.currentTimeMillis();
        n_queen queen = new n_queen();
        executorService.execute(()-> queen.init(1));
        executorService.execute(()-> queen.init(2));
        executorService.execute(()-> queen.init(3));
        executorService.execute(()-> queen.init(4));
        executorService.execute(()-> queen.init(5));
        executorService.execute(()-> queen.init(6));
        executorService.execute(()-> queen.init(7));
        executorService.execute(()-> queen.init(8));
        executorService.execute(()-> queen.init(9));
        executorService.execute(()-> queen.init(10));
        executorService.execute(()-> queen.init(11));
        executorService.execute(()-> queen.init(12));
        executorService.execute(()-> queen.init(13));
        executorService.execute(()-> queen.init(14));
        executorService.execute(()-> queen.init(15));
        executorService.execute(()-> queen.init(16));
        long l3 = System.currentTimeMillis();
        System.out.println(l3-l2 + "\tms");

        Thread.sleep(1000);
        System.out.println("n_queen.total = " + n_queen.total);


    }
}

class n_queen{

    public static int total = 0;
    public void init(int i) {
        int[] stack = new int[20]; // 状态位
        int[] check = new int[20]; // 0: 未使用，1：使用
        stack[0] = i;
        check [i] = 1;
        fun3(16,check,stack,1);
    }

    public void fun3(int N, int[] check, int[] stack, int top){ //
//        System.out.println(1);
        if(top == N){  // n 个元素里面选 r个元素。r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
            synchronized (n_queen.class){
                total++;
            }
            return;
        }
        for (int i = 1; i <= N; i++) {  // n 个元素
            if(check[i] == 0 ){ // r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
                boolean i_isOk = true;
                for (int j = 0; j < top; j++)
                    if(((top+i) == (j+stack[j]) || (top-i) == (j-stack[j]))){  // 列差：低    行差：高
                        i_isOk = false;
                        break;
                    }
                if(i_isOk){
                    check[i] = 1;
                    stack[top++] = i;
                    fun3(N,check,stack,top);
                    top--;
                    check[i] = 0;
                }
            }
        }
    }
}
